package com.gao.alg.geek;

import java.lang.reflect.Array;
import java.util.*;

public class ThreeSum {

    /**
     * 暴力
     * a + b +c = 0
     * a + b = -c
     * 需要先排序：保证数组相同，ArrayList的hash值一样
     * HashSet 排除元素一样的ArrayList
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {

        Set<List<Integer>> list = new HashSet<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if (nums[i]==  -(nums[j] + nums[k])){
                        List<Integer> ls = new ArrayList<>();
                        ls.add(nums[i]);
                        ls.add(nums[j]);
                        ls.add(nums[k]);
                        list.add(ls);
                    }
                }
            }
        }
        return new ArrayList<>(list);
    }
//[[2, -1, -1], [6, -2, -4], [6, -3, -3], [2, 1, -3], [1, 0, -1], [2, 0, -2]]
//[[2, -1, -1], [6, -2, -4], [6, -3, -3], [2, 1, -3], [1, 0, -1], [2, 0, -2]]
//[[-4, -2, 6], [-3, -3, 6], [-3, 1, 2], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]]
    public static void main(String[] args) {
        ThreeSum sum = new ThreeSum();
        int [] arr = new int[]{-1,0,1,2,-1,-4,-3,-3,6,-2};
        List<List<Integer>> lists = sum.threeSum4ByDoublePoint(arr);
        System.out.println(lists);
    }
    public List<List<Integer>> threeSum2(int[] nums) {
        Set<List<Integer>> ret = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int k = 0; k < nums.length-2; k++) {
            for (int i = k+1; i < nums.length-1; i++) {
                for (int j = i+1; j < nums.length; j++) {
                    if (nums[i]+nums[j]+nums[k]== 0){
                        ret.add(sort(nums[k],nums[i],nums[j]));
                    }
                }
            }
        }
        return new ArrayList<>(ret);
    }
    public List<List<Integer>> threeSum3WithCache(int[] nums) {
        Set<List<Integer>> ret = new HashSet<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(-nums[i],i);
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                int t = nums[i]+nums[j];
                if (map.containsKey(t)){
                    int k = map.get(t);
                    if (k !=i && k != j){
                        ret.add(sort(nums[i], nums[j],-t));
                    }
                }
            }
        }
        return new ArrayList<>(ret);
    }

    /**
     * 双指针: 左右向中间夹逼
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum4ByDoublePoint(int[]nums){
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            if (nums[i]>0){
                break;
            }
            if (i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int j = i+1,k = nums.length-1;
            while (k>j){
                int s = nums[i] + nums[j] + nums[k];
                if (s>0){
                    k--;
                    while (k>j && nums[k]==nums[k+1]){
                        k--;
                    }
                }else if (s<0){
                    j++;
                    while (k>j && nums[j]==nums[j-1]){
                        j++;
                    }
                }else {
                    List<Integer> ls = new ArrayList<>();
                    ls.add(nums[i]);
                    ls.add(nums[j]);
                    ls.add(nums[k]);
                    ret.add(ls);
                    j++;
                    k--;
                    while (k>j && nums[k]==nums[k+1]){
                        k--;
                    }
                    while (k>j && nums[j]==nums[j-1]){
                        j++;
                    }
                }
            }
        }
        return ret;
    }

    /**
     * 左右夹逼法，第二遍
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum4ByDoublePoint2(int[]nums){
        if (nums == null || nums.length < 3){
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            if (nums[i]>0){
                break;
            }
            if (i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int j = i+1,k = nums.length -1;
            while (k > j){
                int s = nums[i] + nums[j] +nums[k];
                if (s>0){
                    k--;
                    while (k>j && nums[k]==nums[k+1]){
                        k--;
                    }
                }else if(s<0){
                    j++;
                    while (k>j && nums[j]==nums[j-1]){
                        j++;
                    }
                }else {
                    List<Integer> ls =  new ArrayList<>();
                    ls.add(nums[i]);
                    ls.add(nums[j]);
                    ls.add(nums[k]);
                    ret.add(ls);
                    j++;
                    k--;
                    while (k>j && nums[j]==nums[j-1]){
                        j++;
                    }
                    while (k>j && nums[k]==nums[k+1]){
                        k--;
                    }
                }
            }
        }
        return ret;
    }

    private List<Integer> sort(int k,int i,int j){
        List<Integer> ls = new ArrayList<>();
        if (i > j){
            if (k>i){
                ls.add(k);
                ls.add(i);
                ls.add(j);
            }else {
                ls.add(i);
                if (k>j){
                    ls.add(k);
                    ls.add(j);
                }else {
                    ls.add(j);
                    ls.add(k);
                }
            }
        }else {
            if (k>j){
                ls.add(k);
                ls.add(j);
                ls.add(i);
            }else {
                ls.add(j);
                if (k>i){
                    ls.add(k);
                    ls.add(i);
                }else {
                    ls.add(i);
                    ls.add(k);
                }
            }
        }
        return ls;
    }
}
